//
// Created by Lenovo on 2024/2/27.
//
#include<bits/stdc++.h>
using namespace std;
//所有可能得路径
class Solution {
public:

    vector<vector<int>> res;
    vector<int> list;
    int target;

    void dfs(vector<vector<int>>& graph,int i,vector<bool>& st){
        if(i==target){
            res.push_back(list);
        }
        for(int j=0;j<graph[i].size();j++){
            int node=graph[i][j];
            if(!st[node]){
                st[node]=true;
                list.push_back(node);
                dfs(graph,node,st);
                list.pop_back();
                st[node]= false;
            }
        }
    }

    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        target=graph.size()-1;
        vector<bool> st(graph.size(), false);
        st[0]= true;
        list.push_back(0);
        dfs(graph,0,st);
        return res;
    }
};